package com.muchfish.algorithm.array;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/2vYnGI/description/">LCP 18. 早餐组合</a>
 * <br>
 * 题目描述：
 * 小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。<br>
 * 小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。<br>
 * 解题思路：<br>
 * 排序+双指针法：
 * 1.对staple、drinks进行升序排序
 * 2.创建两个指针，i和j。i指向staple的起点，j指向drinks的终点。
 * 3.若staple[i] + drinks[j] <= x，则符合要求。
 *
 * 这行代码：
 *
 * ```java
 * cnt = (cnt + j + 1) % 1000000007;
 * ```
 *
 * 的作用是对 `cnt` 进行更新，同时确保结果不会超出规定的数值范围，具体可以分为以下几个部分：
 *
 * 1. **`cnt + j + 1`**：在算法中，`cnt` 是一个计数器，表示满足条件的组合数量。`j` 是饮料数组 `drinks` 的下标，代表目前可以与 `staple[i]` 搭配的 `drinks` 数量。因为饮料数组是已经排序的，所以如果 `staple[i] + drinks[j] <= x` 成立，那么从 `0` 到 `j` 的所有饮料都满足该条件，即这些饮料都可以和 `staple[i]` 搭配，因此更新 `cnt` 时加上了 `j + 1`，表示当前 `staple[i]` 可以搭配的饮料组合数量为 `j + 1` 种。
 *
 * 2. **`% 1000000007`**：为了防止 `cnt` 累加后溢出（可能会达到非常大的数值），这里每次更新 `cnt` 时都会对 `1000000007` 取模。取模的作用是保证 `cnt` 不会超过 `1000000007`，并且这是题目要求的结果范围（如果这是竞赛题目常见的情况）。因此，取模确保了结果始终在合法范围内。
 *
 * 总结：
 * - `cnt + j + 1` 计算当前可行的组合数量。
 * - `% 1000000007` 确保计数器 `cnt` 不会超出范围，避免溢出，并保持题目要求的正确格式。
 */
public class Array5 {
    public static void main(String[] args) {
        int[] staple = {10, 20, 5};
        int[] drinks = {5, 5, 2};
        int x = 15;
        int i = breakfastNumber(staple, drinks, x);
        System.out.println("i = " + i);
    }

    public static int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(staple);
        Arrays.sort(drinks);
        int cnt = 0;
        int m = staple.length, n = drinks.length;
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (staple[i] + drinks[j] <= x) {
                cnt = (cnt + j + 1) %   1000000007;
                i++;
            } else {
                j--;
            }
        }
        return cnt % 1000000007;
    }
}
